package com.czk.algorithm.prime.pricatice;

/**
 * @Author:ChenZhangKun
 * @Date: 2020/12/28 21:07
 */
@SuppressWarnings("all")
public class Prime {
    public static void main(String[] args) {
        // 顶点数
        char[] data = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        // 个数
        int verx = data.length;
        // 10000这个大数表示两个点不连通
        int[][] weight = {{10000, 5, 7, 10000, 10000, 10000, 2}, {5, 10000, 10000, 9, 10000, 10000, 3},
                {7, 10000, 10000, 10000, 8, 10000, 10000}, {10000, 9, 10000, 10000, 100000, 4, 10000},
                {10000, 10000, 10000, 8, 10000, 10000, 5, 4}, {10000, 10000, 1000, 4, 5, 10000, 6}, {2, 3, 10000, 10000, 4, 5, 10000}};
        PrimeGraph graph = new PrimeGraph(data, weight);
        Tree tree = new Tree(graph);
        tree.miniTree(0);
    }
}

/**
 * 树
 */
class Tree {
    private PrimeGraph graph;

    public Tree(PrimeGraph graph) {
        this.graph = graph;
    }

    public void miniTree(int start) {
        int totalLength = 0;
        // 创建顶点集合
        // 0 表示未访问，1表示已经访问
        int[] isVisited = new int[graph.length];
        // 开始顶点标记为已经访问
        isVisited[start] = 1;
        // 指向顶点的指针
        int h1 = -1;
        int h2 = -1;
        // n个顶点有n-1条边
        // 临时变量
        int temp = 10000;
        for (int k = 1; k < graph.length; k++) {
            // 表示第一个指针
            for (int i = 0; i < graph.length; i++) {
                // 表示第二个指针
                for (int j = 0; j < graph.length; j++) {
                    // 判断距离
                    if (isVisited[i] == 1 && isVisited[j] == 0 && graph.data[i][j] < temp) {
                        temp = graph.data[i][j];
                        // 指针下移动
                        h1 = i;
                        h2 = j;
                    }
                }
            }
            isVisited[h2] = 1;
            System.out.println("先连接 " + graph.vertex[h1] + " 和 " + graph.vertex[h2] + " 他们之间的距离是 " + temp);
            totalLength += temp;
            temp = 10000;
        }
        System.out.println("===========");
        System.out.println("最小生成树的总距离是 " + totalLength);
    }
}

/**
 * 图
 */
class PrimeGraph {
    /**
     * 顶点
     */
    char[] vertex;
    /**
     * 边数
     */
    int length;
    /**
     * 邻接矩阵
     */
    int[][] data;

    public PrimeGraph(char[] vertex, int[][] data) {
        this.vertex = vertex;
        this.data = data;
        this.length = vertex.length;
    }
}
